package leetcode.code0375;

public class Solution3753 {

	public int getMoneyAmount(int n) {
		int[][] dp = new int[n + 1][n + 1];
		for (int l = n - 1; l >= 1; l--) {
			for (int r = l + 1; r <= n; r++) {
				int ans = Integer.MAX_VALUE;
				for (int i = l; i < r; i++) {// 当前选i，即以i为左右树的头
					int left = dp[l][i - 1];// 左子树的最小代价
					int right = dp[i + 1][r];// 右子树的最小代价
					int cur = Math.max(left, right) + i;// 在经历左右最小代价情况下，最大的是选i不得不承受的`痛`
					ans = Math.min(ans, cur);// [l,r]范围内所有`痛`中最小的，是f的最小代价
				}
				dp[l][r] = ans;
			}
		}
		return dp[1][n];
	}

//	private void f(int l, int r) {
//		int ans = Integer.MAX_VALUE;
//		for (int i = l; i <= r; i++) {// 当前选i，即以i为左右树的头
//			int left = this.f(l, i - 1);// 左子树的最小代价
//			int right = this.f(i + 1, r);// 右子树的最小代价
//			int cur = Math.max(left, right) + i;// 在经历左右最小代价情况下，最大的是选i不得不承受的`痛`
//			ans = Math.min(ans, cur);// [l,r]范围内所有`痛`中最小的，是f的最小代价
//		}
//	}

	public static void main(String[] args) {
		Solution3753 so = new Solution3753();
		int ans = so.getMoneyAmount(10);
		System.out.println(ans);
	}
}
